import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private WeightedQuickUnionUF uf1;
    private int n;
    private byte[] site;
    private int numOpenSites;

    public Percolation(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException();
        }
        uf1 = new WeightedQuickUnionUF(n * n + 1);
        // uf2 = new WeightedQuickUnionUF(n * n + 1);
        this.n = n;
        site = new byte[n * n + 1];
    }

    public void open(int row, int col) {
        int cur, up, down, left, right, root, curRoot;

        validateIndices(row, col);

        cur = (row - 1) * n + col - 1;

        if (site[cur] != 0) {
            return;
        }

        site[cur] = 1;
        ++numOpenSites;

        if (row == 1) {
            uf1.union(cur, n * n);
        }
        if (row == n) {
            site[cur] = 2;
        }

        up = cur - n;
        down = cur + n;
        left = cur - 1;
        right = cur + 1;

        if (up >= 0 && site[up] != 0) {
            root = uf1.find(up);
            curRoot = uf1.find(cur);
            uf1.union(cur, up);
            if (site[root] == 2 || site[curRoot] == 2) {
                site[uf1.find(cur)] = 2;
            }
        }

        if (down < n * n && site[down] != 0) {
            root = uf1.find(down);
            curRoot = uf1.find(cur);
            uf1.union(cur, down);
            if (site[root] == 2 || site[curRoot] == 2) {
                site[uf1.find(cur)] = 2;
            }
        }

        if ((left + 1) % n != 0 && site[left] != 0) {
            root = uf1.find(left);
            curRoot = uf1.find(cur);
            uf1.union(cur, left);
            if (site[root] == 2 || site[curRoot] == 2) {
                site[uf1.find(cur)] = 2;
            }
        }

        if (right % n != 0 && site[right] != 0) {
            root = uf1.find(right);
            curRoot = uf1.find(cur);
            uf1.union(cur, right);
            if (site[root] == 2 || site[curRoot] == 2) {
                site[uf1.find(cur)] = 2;
            }
        }

    }

    public boolean isOpen(int row, int col) {
        validateIndices(row, col);

        int cur = (row - 1) * n + col - 1;
        return site[cur] == 0 ? false : true;
    }

    public boolean isFull(int row, int col) {
        validateIndices(row, col);
        int cur = (row - 1) * n + col - 1;
        if (site[cur] == 0) {
            return false;
        } else if (uf1.connected(cur, n * n)) {
            return true;
        }
        return false;
    }

    public int numberOfOpenSites() {
        return numOpenSites;
    }

    public boolean percolates() {
        return site[uf1.find(n * n)] == 2 ? true : false;
    }

    private void validateIndices(int row, int col) {
        if (row < 1 || row > n || col < 1 || col > n) {
            throw new IndexOutOfBoundsException("row index i out of bounds");
        }
    }

    public static void main(String[] args) {

    }
}